﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace MathSolution
{
    /// <summary>
    /// Mathematical approach: 
    /// Compute the prime factorization of each number from 1 to 20, 
    /// and multiply the greatest power of each prime together
    /// 
    /// Implementation approach (http://projecteuler.net/index.php?section=forum&id=5&page=17):
    /// 26 Feb 2008 06:20 pm 
    /// MichaelBlondin   (C#)  
    /// Primes lower than 20 are 2,3,5,7,11,13,17,19 
    /// Their highest powers are 16,9,5,7,11,13,17,19 
    /// So the smallest number that is divisible by all 
    /// of the numbers from 1 to 20 is 16*9*5*7*11*13*17*19 = 232792560
    /// </summary>
    internal class Program
    {
        private static void Main()
        {
            var maxNumber = 20;
            var highestPowers = new List<int>();
            var time = new Stopwatch();

            time.Start();
            foreach (var i in PrimeNumbersUntil(maxNumber))
            {
                highestPowers.Add(FindHighestPower(i, maxNumber));
            }
            time.Stop();

            Console.WriteLine(highestPowers.Product());
            Console.WriteLine("Execution time: {0}ms", time.ElapsedMilliseconds);

            Console.ReadKey();
        }

        private static int FindHighestPower(int number, int maxNumber)
        {
            if(number > maxNumber)
                throw new InvalidOperationException("Number cannot be greater than max number.");

            var highestPower = number;

            for(int power = 1; power <= maxNumber; power++)
            {
                if (Math.Pow(number, power) > maxNumber)
                    break;

                highestPower = (int) Math.Pow(number, power);
            }

            return highestPower;
        }

        private static IEnumerable<int> PrimeNumbersUntil(int maxNumber)
        {
            yield return 2; // Known prime number

            for (int number = 3; number <= maxNumber; number += 2)
            {
                if (IsPrime(number))
                    yield return number;
            }
        }


        private static readonly Func<int, bool> IsPrime = number =>
        {
            for (int divisor = 2; divisor <= Math.Sqrt(number); divisor++)
            {
                if (0 == number % divisor)
                    return false;
            }

            return true;
        };
    }
}
